// Copyright 2010 Keir Mierle. All rights reserved.
//
// A simple transposition table based on the algorithm described in the paper:
//
//   Dennis Breuker, Jos Uiterwijk and Jaap van den Herik (1994). Replacement
//   Schemes for Transposition Tables. ICCA Journal, Vol. 17, No. 4
//
// This generalizes the two level table to N-level in a straightforward manner.
// There are more sophisticated transposition table methods possible that use
// clever garbage collection schemes. These are briefly discussed in
// Kishimoto's thesis. I've decided not to bother with them at this time, as
// the simple implementation below works fine.

#ifndef TT_H
#define TT_H

#include <vector>
#include <limits>
#include "inttypes.h"

template<typename Key, typename Value, int kBucketSize = 3>
struct TranspositionTable {
  TranspositionTable(int size) : table(kBucketSize * size) {}

  void Store(const Key &key, const Value &value, uint64 score) {
    int bucket = kBucketSize * (key % (table.size() / kBucketSize));
    int to_replace = -1;

    // Is there an existing entry for this key?
    for (int i = 0; i < kBucketSize; ++i) {
      if (table[bucket + i].key == key) {
        to_replace = i;
        break;
      }
    }

    // Is there an empty spot?
    if (to_replace == -1) {
      for (int i = 0; i < kBucketSize; ++i) {
        if (table[bucket + i].key == Key(0)) {
          to_replace = i;
          break;
        }
      }
    }

    // If replacement is required, replace the lowest scoring entry.
    if (to_replace == -1) {
      uint64 smallest_score = numeric_limits<uint64>::max();
      for (int i = 0; i < kBucketSize; ++i) {
        if (table[bucket + i].score < smallest_score) {
          smallest_score = table[bucket + i].score;
          to_replace = i;
        }
      }
    }
    table[bucket + to_replace].key = key;
    table[bucket + to_replace].value = value;
    table[bucket + to_replace].score = score;
  }

  Value *Lookup(const Key &key, uint64 *score = NULL) {
    int bucket = kBucketSize * (key % (table.size() / kBucketSize));
    for (int i = 0; i < kBucketSize; ++i) {
      if (table[bucket + i].key == key) {
        if (score) {
          *score = table[bucket + i].score;
        }
        return &(table[bucket + i].value);
      }
    }
    return NULL;
  }

  struct Entry {
    Entry() : key(0) {}
    Key key;
    Value value;
    uint64 score;
  };

  std::vector<Entry> table;
};

#endif  // TT_H
